package bucketsort;

import org.junit.jupiter.api.Test;

import java.text.NumberFormat;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;
import java.util.stream.IntStream;

/**
 * 基数排序
 */
public class RadixSort {

    NumberFormat num = NumberFormat.getInstance();

    static int count = 0;

    @Test
    public void client() {
        Random random = new Random(1);
        for (int i = 0; i < 500000; i++) {
            /**
             * 随机样本长度
             */
            int anInt = random.nextInt(100) + 1;
            int[] arr = new int[anInt];
            for (int j = 0; j < anInt; j++) {
                /**
                 * 随机样本数据
                 */
                arr[j] = random.nextInt(100);
            }
            System.out.println("=======================第" + (i + 1) + "次=======================");
            System.out.println("排序前==》" + Arrays.toString(arr));
            radixSort(arr);
            System.out.println("排序后==》" + Arrays.toString(arr));
            int[] newArr = Arrays.copyOf(arr, arr.length);
            boolean logarithmizer = logarithmizer(arr, newArr);
            if (logarithmizer) {
                System.out.println("对数器验证结果：PASS");
            } else {
                System.out.println("对数器验证结果：NOT PASS");
            }
        }

        System.out.println("==============================================");
        System.out.println("=======                                 ======");
        System.out.println("=======    验证不通过结果为：" + count + "   ======");
        System.out.println("=======                                 ======");
        System.out.println("==============================================");
    }

    /**
     * 根据最大位数，对每一个数据进行分桶
     * 比如：第一次循环，个位为1的数据存放进下标为1的桶的队列中…………
     *      第二次循环，十位为1的数据存放进下标为1的桶的队列中…………
     *      …………
     */
    private void radixSort(int[] arr) {
        // 创建一个大小为10的数组作为桶
        ArrayList<ArrayDeque<String>> bucket = new ArrayList<>(10);
        for (int i = 0; i < 10; i++) {
            // 桶中每个位置上存放一个和原数组等长的队列
            ArrayDeque<String> da = new ArrayDeque<>(arr.length);
            bucket.add(da);
        }

        String[] str = new String[arr.length];
        // 获取原数组中最大数据是几位数
        int max = IntStream.of(arr).max().getAsInt();
        int maxLeg = String.valueOf(max).length();
        num.setMinimumIntegerDigits(maxLeg);
        // 原数组中其他数据不够最大数据的位数时，前边补充0补足位数。
        for (int i = 0; i < arr.length; i++) {
            String data = String.valueOf(arr[i]);
            if (data.length() < maxLeg) {
                data = num.format(arr[i]);
            }
            str[i] = data;
        }

        /**
         * 根据最大位数，对每一个数据进行分桶
         * 比如：第一次循环，个位为1的数据存放进下标为1的桶的队列中…………
         *      第二次循环，十位为1的数据存放进下标为1的桶的队列中…………
         *      …………
         */
        for (int i1 = maxLeg - 1; i1 > - 1; i1--) {
            // 根据最大位数，对每一个数据进行分桶
            for (String s : str) {
                int da = Integer.parseInt(String.valueOf(s.charAt(i1)));
                bucket.get(da).add(s);
            }

            int index = 0;
            /**
             * 第一次循环，按照个位分桶后对数组还原…………
             * 第二次循环，按照十位分桶后对数组还原…………
             * …………
             */
            for (ArrayDeque<String> arrayDeque : bucket) {
                while (!arrayDeque.isEmpty()) {
                    str[index++] = arrayDeque.poll();
                }
            }
        }

        // 最后将完全处理好的数组，覆盖到最原始的数据中，做到原数组有序
        for (int i = 0; i < str.length; i++) {
            arr[i] = Integer.parseInt(str[i]);
        }
    }

    /**
     * 对数器验证：思想，用java提供的工具类和我们自己写的算法对处理后的数组，
     * 进行每一个元素比对。
     */
    private static boolean logarithmizer(int[] arr, int[] newArr) {
        /**
         * java提供的工具类
         */
        Arrays.sort(newArr);
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != newArr[i]) {
                count++;
                return false;
            }
        }

        return true;
    }
}
